/**
 *  Copyright (C) 2013  Piotr Szczepa�ski
 *
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/
package edu.pw.elka.gtsna.graph;

import java.util.LinkedHashSet;
import java.util.Set;

import edu.pw.elka.gtsna.community_detection.CommunityStructure;
import edu.pw.elka.gtsna.graph_creator.GraphCreator;

/**
 * @author Piotr Lech Szczepa�ski
 * @author P.Szczepanski@ii.pw.edu.pl 
 *
 */
public class DirectedGraph extends Graph {

	private Set<Integer>[] graphInNeighbours;

	@SuppressWarnings("unchecked")
	public DirectedGraph(int numOfNodes){
		super(numOfNodes);
		graphInNeighbours = new Set[numOfNodes+1];
		for (int i = 1; i<= numOfNodes; i++){
			graphInNeighbours[i] = new LinkedHashSet<Integer>();
		}
	}
	
	public DirectedGraph(GraphCreator creator){	
		this(creator.getNumOfNodes());
			
		for(Edge e: creator){
			addEdge(e);
		}
	}
	
	/**
	 * @param directedGraph
	 */
	public DirectedGraph(DirectedGraph directedGraph) {
		super(directedGraph);
		
		for (int node: directedGraph.getAllNodes()){
			graphInNeighbours[pos(node)] = new LinkedHashSet<Integer>(directedGraph.getInNeigbours(node));
		}
	}

	public int getAmongPartitionInDegree(int node, CommunityStructure partition){
		int degree = 0;
		boolean checked[] = new boolean[partition.size()];
		for(int neighbour: getInNeigbours(node)){
			if (!checked[partition.getNodeCommunityNumber(neighbour)]){
				degree++;
				checked[partition.getNodeCommunityNumber(neighbour)] = true;
			}
		}
		// do not count nodes from the same cs
		if (checked[partition.getNodeCommunityNumber(node)]) {
			degree--;
		}
		return degree;
	}
	
	public int getWithinPartitionInDegree(int node, int partitionNumber, CommunityStructure partition){
		int degree = 0;
		for(int neighbour: getInNeigbours(node)){
			if (partitionNumber == partition.getNodeCommunityNumber(neighbour)){
				degree++;
			}
		}
		return degree;
	}
	
	public Set<Integer> getOutNeigbours(int node){
		return getNeigbours(node);
	}
	
	public Set<Integer> getInNeigbours(int node){
		return graphInNeighbours[node];
	}
	
	public int getInDegree(int node){
		return graphInNeighbours[node].size();
	}
	
	public int getOutDegree(int node){
		return getDegree(node);
	}
	
	
	public int getAmongPartitionOutDegree(int node, CommunityStructure partition){
		return getInterCommunityDegree(node, partition);
	}
	
	public int getWithinPartitionOutDegree(int node, int partitionNumber, CommunityStructure partition){
		return getIntraCommunityDegree(node, partition, partitionNumber);
	}
	
	
	public void addEdge(int u, int v){
		super.addEdge(u, v);
		graphInNeighbours[v].add(u);
	}

	public void removeEdge(int u, int v){
		super.removeEdge(u, v);
		graphInNeighbours[v].remove(u);
	}
	
	/**
	 * 
	 * @param subgraph - the set of vertices
	 * @return the set of vertices incident to all vertices from subgraph. 
	 * 		   NOTE: The vertices from the set subgraph are excluded from return
	 */
	public Set<Integer> getInNeigbours(Set<Integer> subgraph){
		Set<Integer> neigbours = new LinkedHashSet<Integer>();
		for(int i : subgraph) {
			for (int u: getInNeigbours(i)){
				if (!subgraph.contains(u)) {
					neigbours.add(u);
				}
			}
		}
		return neigbours;
	}
	
	public int getInterPartitionInDegree(int node, CommunityStructure partition){
		int degree = 0;
		for(int neighbour: getInNeigbours(node)){
			if (partition.getNodeCommunityNumber(node) != partition.getNodeCommunityNumber(neighbour)){
				degree++;
			}
		}
		return degree;
	}
	
	public int getInterPartitionOutDegree(int node, CommunityStructure partition){
		return getInterPartitionDegree(node, partition);
	}

	/* (non-Javadoc)
	 * @see edu.pw.elka.gtsna.graph.Graph#clone()
	 */
	@Override
	public Graph clone() throws CloneNotSupportedException
	{
		Graph clonedObj = null;

		clonedObj= new DirectedGraph(this);
		return clonedObj;
	}
	
}
